Biến đổi walsh fourier là gì? Nghiên cứu khoa học liên quan

Giới thiệu tổng quan về biến đổi Walsh-Fourier

Biến đổi Walsh-Fourier (WFT) là một phương pháp biến đổi toán học dùng để biểu diễn tín hiệu theo các hàm cơ sở rời rạc dạng nhị phân, thường là các hàm vuông. Không giống như biến đổi Fourier truyền thống sử dụng sóng hình sin và cosin liên tục, WFT sử dụng các hàm Walsh – các hàm trực giao rời rạc nhận giá trị ±1 theo từng đoạn.

WFT được ứng dụng trong các lĩnh vực xử lý tín hiệu, truyền thông số, học máy, phân tích ảnh, lý thuyết thông tin và mật mã học. Điểm nổi bật của WFT là không cần tính toán lượng giác, giúp tối ưu hóa hiệu suất tính toán trên phần cứng nhúng hoặc thiết bị tài nguyên hạn chế.

Các ứng dụng điển hình của Walsh-Fourier bao gồm: trích xuất đặc trưng ảnh trong thị giác máy tính, lọc nhiễu tín hiệu nhị phân, mã hóa dữ liệu trong truyền hình số và radar xung nhịp cao. Nhiều hệ thống cũng sử dụng biến thể Walsh-Hadamard transform (WHT) để đạt hiệu suất cao trong nén dữ liệu thời gian thực.

Cơ sở toán học của biến đổi Walsh

Các hàm Walsh là một tập hợp các hàm vuông trực giao nhận giá trị ±1 trên miền [0,1], được xác định thông qua biểu diễn nhị phân và sự đảo bit. Hàm Walsh có thể được định nghĩa bằng cách sắp xếp các hàng của ma trận Hadamard theo trật tự Gray-code hoặc trật tự thứ tự tự nhiên (sequency).

Ma trận Hadamard cấp $2^n$ được xây dựng theo quy tắc đệ quy như sau: $H_1 = \begin{bmatrix} 1 \end{bmatrix}, \quad H_{2^n} = \begin{bmatrix} H_{2^{n-1}} & H_{2^{n-1}} \\ H_{2^{n-1}} & -H_{2^{n-1}} \end{bmatrix}$

Ví dụ, ma trận Hadamard cấp 4: $H_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix}$

Mỗi hàng của ma trận này đại diện cho một hàm Walsh. Tập các hàm này tạo thành một cơ sở trực giao trong không gian rời rạc, cho phép biểu diễn bất kỳ tín hiệu số nhị phân hoặc rời rạc nào như tổ hợp tuyến tính của các hàm Walsh.

So sánh biến đổi Walsh và biến đổi Fourier truyền thống

Biến đổi Fourier biểu diễn tín hiệu dựa trên sóng hình sin và cosin – hàm liên tục, tuần hoàn và có tính trơn. Trong khi đó, Walsh transform sử dụng sóng vuông không liên tục, giúp tăng tính cục bộ và phù hợp với tín hiệu nhị phân hoặc có biên độ thay đổi đột ngột.

Khác biệt rõ nhất giữa hai hệ cơ sở là:

• Fourier: Liên tục, tuần hoàn, phức tạp khi xử lý tín hiệu không trơn tru
• Walsh: Rời rạc, vuông, phù hợp với các tín hiệu số, không tuần hoàn

Bảng so sánh dưới đây tóm tắt một số khác biệt chính:

Tiêu chí	Biến đổi Fourier	Biến đổi Walsh
Cơ sở toán học	Sine/Cosine	Hàm vuông ±1
Tín hiệu phù hợp	Liên tục, tuần hoàn	Rời rạc, nhị phân
Ứng dụng	Phân tích tần số, âm thanh	Mã hóa nhị phân, học máy
Khả năng cục bộ hóa	Thấp	Cao
Yêu cầu lượng giác	Có	Không

Thuật toán và tính toán biến đổi Walsh-Fourier

Để tính Walsh transform nhanh, ta sử dụng thuật toán Fast Walsh-Hadamard Transform (FWHT), có cấu trúc đệ quy tương tự như FFT trong biến đổi Fourier. Thuật toán này hoạt động hiệu quả với tín hiệu có độ dài là lũy thừa của 2, sử dụng phép cộng và trừ thay vì lượng giác.

Độ phức tạp tính toán FWHT là: $\mathcal{O}(n \log_2 n)$ trong khi FFT có độ phức tạp tương đương nhưng tốn tài nguyên xử lý hơn vì phải dùng số phức và lượng giác.

FWHT phù hợp để triển khai trên FPGA, vi điều khiển, các hệ thống thời gian thực vì không yêu cầu phép nhân hoặc bảng tra cứu lượng giác, đồng thời có thể song song hóa hiệu quả. Một chuỗi dữ liệu đầu vào được chia đôi và xử lý theo nguyên tắc butterfly (bướm) như sau:

• Gộp giá trị: $x_1 + x_2$
• Hiệu giá trị: $x_1 - x_2$
• Lặp lại với cấp độ cao hơn

FWHT được dùng trong nén ảnh, trích xuất đặc trưng, nhận dạng mẫu, lọc tín hiệu đa cấp và hệ thống radar nhịp xung cao.

Ứng dụng trong xử lý tín hiệu số

Biến đổi Walsh-Fourier được áp dụng rộng rãi trong xử lý tín hiệu số (DSP) nhờ khả năng phân tích và tổng hợp tín hiệu rời rạc mà không yêu cầu các phép toán lượng giác. Đặc biệt, WFT phù hợp với các tín hiệu dạng nhị phân, tín hiệu biến thiên đột ngột hoặc phi tuần hoàn – những trường hợp mà biến đổi Fourier truyền thống tỏ ra kém hiệu quả.

Trong truyền thông số, Walsh functions được sử dụng để tạo ra các dãy trực giao cho đa truy cập phân chia theo mã (CDMA), ví dụ như trong hệ thống CDMA2000. Ở đây, các kênh truyền độc lập có thể chia sẻ cùng một băng thông nhờ sử dụng các dãy Walsh khác nhau để mã hóa thông tin.

Trong hệ thống radar xung và siêu âm y học, Walsh transform được dùng để lọc nhiễu và phân tích sóng phản hồi. Đối với tín hiệu ảnh, WFT có thể trích xuất biên và chi tiết nhỏ mà không làm mất thông tin cấu trúc như các phép lọc tuyến tính thông thường.

Ứng dụng trong lý thuyết thông tin và mật mã

Trong mật mã học, Walsh transform đóng vai trò quan trọng trong việc phân tích độ phi tuyến của các hàm Boolean. Một hàm Boolean có độ phi tuyến càng cao thì càng khó bị tấn công bằng các kỹ thuật tuyến tính – một tiêu chí bảo mật quan trọng trong thiết kế hệ thống mã hóa.

Độ phi tuyến $NL(f)$ của một hàm Boolean $f$ có thể được tính từ phổ Walsh như sau: $NL(f) = 2^{n-1} - \frac{1}{2} \max_{w \in \{0,1\}^n} |W_f(w)|$ trong đó $W_f(w)$ là biến đổi Walsh của hàm $f$ theo vector $w$.

Các ứng dụng khác của WFT trong lý thuyết thông tin bao gồm:

• Phân tích mã kênh (channel coding) và các mã tuyến tính như Reed-Muller
• Xác định tính cân bằng và tuyến tính của hàm mã hóa
• Phát hiện lỗi trong truyền dẫn dữ liệu bằng cách so sánh phổ Walsh

Ứng dụng trong thị giác máy tính và học máy

Biến đổi Walsh được ứng dụng trong thị giác máy tính như một phương pháp trích xuất đặc trưng ảnh nhanh và hiệu quả, đặc biệt hữu ích trong môi trường ánh sáng thay đổi mạnh hoặc nhiễu cao. Các đặc trưng Walsh giúp mã hóa biên và kết cấu ảnh một cách gọn nhẹ, rất phù hợp với thiết bị nhúng.

Trong học máy, đặc biệt là mạng nơ-ron nhị phân (Binary Neural Networks - BNNs), Walsh transform được dùng để chuyển đổi các trọng số và đầu vào sang miền Walsh nhằm tăng tốc độ huấn luyện và giảm chi phí lưu trữ. Walsh basis cũng được khai thác trong các thuật toán rút trích đặc trưng đơn giản hóa đầu vào trước khi đưa vào mô hình học sâu.

Các nghiên cứu gần đây cho thấy Walsh transform có thể kết hợp với mạng tích chập (CNNs) để xây dựng hệ thống nhận dạng nhẹ, chạy tốt trên thiết bị IoT và không cần GPU.

Mở rộng và biến thể hiện đại

Các biến thể hiện đại của Walsh-Fourier bao gồm Walsh-Hartley transform (WHT), generalized Walsh transform và quantum Walsh-Hadamard transform – biến đổi cơ sở trong nhiều thuật toán lượng tử. Đặc biệt, trong điện toán lượng tử, phép biến đổi Walsh-Hadamard là bước khởi tạo trong thuật toán Grover và Deutsch–Jozsa.

Trong phần cứng nhúng, biến đổi Walsh được tối ưu hóa để chạy trên FPGA và DSP thông qua kiến trúc butterfly đơn giản. Điều này giúp triển khai các bộ mã hóa/giải mã Walsh trong thời gian thực với độ trễ thấp và mức tiêu thụ năng lượng thấp – phù hợp với hệ thống radar di động, thiết bị cảm biến thông minh và vi xử lý trong robot tự hành.

Các hướng nghiên cứu mở rộng gồm:

• Kết hợp Walsh transform với wavelet hoặc Fourier hybrid
• Thiết kế hệ mã hoá lượng tử dùng nền Walsh
• Triển khai hệ thống học sâu lượng tử sử dụng cơ sở Walsh

Tài liệu tham khảo

• Shukla et al., Walsh–Fourier Analysis and Signal Processing, ScienceDirect, 2020
• NIST – Fast Walsh-Hadamard Transform Algorithm
• IEEE – Efficient Implementation of Walsh Transforms on FPGA
• Springer – Applications of Walsh Transform in Computer Vision
• Cleve et al., Quantum Algorithms using Walsh-Hadamard Transform, arXiv